package day23;

import java.util.Scanner;

/**
 * 计算字符串的编辑距离
 */

/**
 * Levenshtein距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，
 * 插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance 。
 * 例如:
 * 字符串A: abcdefg字符串B: abcdef
 * 通过增加或是删掉字符"g”的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
 * 要求:
 * 给定任意两个字符串，写出一个算法计算它们的编辑距离。
 * 数据范围:给定的字符串长度满足1≤len( str) ≤1000
 */

//// 注意类名必须为 Main, 不要有任何 package xxx 信息
//public class Main {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        String s1 = scanner.next();
//        String s2 = scanner.next();
//
//        if (s1.contains(s2)){
//            System.out.println(s1.length() - s2.length());
//        }
//        int len1 = s1.length();
//        int len2 = s2.length();
//
//        int dp[][] = new int[len1][len2];
//
//        //初始化
//        for (int i = 1; i < len1; i++) {
//            dp[0][i] = i;
//        }
//        for (int i = 1; i < len2; i++) {
//            dp[i][0] = i;
//        }
//
//        for (int i = 0; i < len1; i++) {
//            for (int j = 0; j < len2; j++) {
//
//            }
//        }
//    }
//}
import java.util.*;

public class Main {
    //动态规划
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();
        int len1 = s1.length(),len2 = s2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        //初始化
        for(int i = 1;i <= len2;i++) {
            dp[0][i] = i;
        }
        for(int i = 1;i <= len1;i++) {
            dp[i][0] = i;
        }
        for(int i = 1;i <= len1;i++){
            for(int j = 1;j<= len2;j++){
                if(s1.charAt(i - 1) == s2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    //替换
                    dp[i][j] = dp[i][j] == 0 ? dp[i - 1][j - 1] + 1 : Math.min(dp[i - 1][j - 1] + 1,dp[i][j]);
                    //插入
                    dp[i][j] = Math.min(dp[i][j - 1] + 1,dp[i][j]);
                    //删除
                    dp[i][j] = Math.min(dp[i - 1][j] + 1,dp[i][j]);
                }
            }
        }
        System.out.println(dp[len1][len2]);
    }
}